package com.quickSort;

import com.Sort;

/**
 * @author 罗俊华
 * @date 2021/5/12 - 8:59 上午
 * 三向切分快速排序
 */
public class QuickSort3Way<Item extends Comparable<Item>> extends Sort<Item> {

    @Override
    public void sort(Item[] comparableArray) {
        this.sort(comparableArray, 0, comparableArray.length - 1);
    }

    /**
     * 在 array[low] 到 array[lessThan-1] 之间的元素都小于 array[lessThan] 到 array[greaterThan] 之间的元素
     * 而 array[lessThan] 到 array[greaterThan] 之间的元素全部都相同，全部作为中轴，不参与下一次递归中的排序（已经完全相同就不参与排序了）
     * 在 array[greaterThan+1] 到 array[high] 之间的元素都大于 array[lessThan] 到 array[greaterThan] 之间的元素
     *
     * @param array
     * @param low
     * @param high
     */
    private void sort(Item[] array, int low, int high) {

        if (high <= low) {
            return;
        }

        /**
         * 最低的一位作为比较的基准（中轴），lessThan会向后移动，
         *
         */
        int lessThan = low;

        /**
         * greaterThan+1 到 high 之间的元素都是要参与到下一次快速排序的元素
         */
        int greaterThan = high;

        /**
         * 比较元素的指针：从 low + 1位开始比较
         */
        int i = low + 1;

        while (i <= greaterThan) {

            int result = array[i].compareTo(array[lessThan]);

            if (result < 0) {
                /**
                 * i指向的元素比基准元素array[lessThan]小，那么就把它和 lessThan 交换，
                 * 然后将 lessThan往后移动，以指向原来的基准值，i也向后移动，比较下一个元素
                 */
                super.exchange(array, i++, lessThan++);

            } else if (result > 0) {
                /**
                 * i指向的元素比基准元素 array[lessThan] 大，那么就把它和 greaterThan 交换，
                 * 然后将 greaterThan 往前移动来标记这个比基准值大的元素要参与下一此递归比较
                 * i不+1的原因是：因为把greaterThan交换过来后，greaterThan 的大小是未知的，要继续进行判断
                 */
                super.exchange(array, i, greaterThan--);

            } else {
                /**
                 * i指向的值和 lessThan 的值一样，那么为了能使这个值后续不参与递归比较，就不移动 lessThan greaterThan
                 * */
                i++;
            }

        }

        this.sort(array, low, lessThan - 1);
        this.sort(array, greaterThan + 1, high);

    }
}
